package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

import java.math.BigDecimal;
import java.util.Locale;

/**
 * 树的子结构
 *
 * @author yuhushuan
 * @date 2020/6/18 21:09
 */
public class _26_1_SubstructureInTree {
    private static boolean hasSubTree(BinaryTreeNode root1, BinaryTreeNode root2) {
        boolean result = false;
        if (root1 != null && root2 != null) {
            if (equals(root1.value, root2.value)) {
                result = doesTree1HaveTree2(root1, root2);
            }
            if (!result) {
                result = hasSubTree(root1.left, root2);
            }
            if (!result) {
                result = hasSubTree(root1.right, root2);
            }
        }
        return result;
    }

    private static boolean doesTree1HaveTree2(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (equals(root1.value, root2.value)) {
            return doesTree1HaveTree2(root1.left, root2.left)
                    && doesTree1HaveTree2(root1.right, root2.right);
        }
        return false;
    }

    private static boolean equals(int i1, int i2) {
        return i1 == i2;
    }

    private static boolean equals(double d1, double d2) {
        BigDecimal b1 = new BigDecimal(d1);
        BigDecimal b2 = new BigDecimal(d2);
        return b1.equals(b2);
    }

    public static void main(String[] args) {
        // 功能测试
        // A 和 B 都是普通的二叉树；B 是 A 的子结构
        test1();
        // A 和 B 都是普通的二叉树；B 不是 A 的子结构
        test2();

        // 特殊输入测试
        // A 的根节点为null
        // B 的根节点为null
    }

    private static void test1() {
        BinaryTreeNode A = new BinaryTreeNode(8);

        BinaryTreeNode a2_8 = new BinaryTreeNode(8);
        BinaryTreeNode a2_7 = new BinaryTreeNode(7);

        BinaryTreeNode a3_9 = new BinaryTreeNode(9);
        BinaryTreeNode a3_2 = new BinaryTreeNode(2);

        BinaryTreeNode a4_4 = new BinaryTreeNode(4);
        BinaryTreeNode a4_7 = new BinaryTreeNode(7);

        A.left = a2_8;
        A.right = a2_7;
        a2_8.left = a3_9;
        a2_8.right = a3_2;
        a3_2.left = a4_4;
        a3_2.right = a4_7;

        BinaryTreeNode B = new BinaryTreeNode(8);

        BinaryTreeNode b2_9 = new BinaryTreeNode(9);
        BinaryTreeNode b2_2 = new BinaryTreeNode(2);

        B.left = b2_9;
        B.right = b2_2;

        print(A, B);

    }

    private static void test2() {
        BinaryTreeNode A = new BinaryTreeNode(8);

        BinaryTreeNode a2_8 = new BinaryTreeNode(8);
        BinaryTreeNode a2_7 = new BinaryTreeNode(7);

        BinaryTreeNode a3_9 = new BinaryTreeNode(9);
        BinaryTreeNode a3_2 = new BinaryTreeNode(2);

        BinaryTreeNode a4_4 = new BinaryTreeNode(4);
        BinaryTreeNode a4_7 = new BinaryTreeNode(7);

        A.left = a2_8;
        A.right = a2_7;
        a2_8.left = a3_9;
        a2_8.right = a3_2;
        a3_2.left = a4_4;
        a3_2.right = a4_7;

        BinaryTreeNode B = new BinaryTreeNode(8);

        BinaryTreeNode b2_9 = new BinaryTreeNode(9);
        BinaryTreeNode b2_2 = new BinaryTreeNode(3);

        B.left = b2_9;
        B.right = b2_2;

        print(A, B);
    }

    private static void print(BinaryTreeNode root1, BinaryTreeNode root2) {
        System.out.println(String.format(Locale.getDefault(),
                "二叉树 %d 是二叉树 %d 的子结构为：%b",
                root2.value, root1.value, hasSubTree(root1, root2)));
    }

}
